# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
root=TreeNode(7)
root.left=TreeNode(3)
root.right=TreeNode(15)
root.right.left=TreeNode(9)
root.right.right=TreeNode(20)
class BSTIterator:

    def __init__(self, root: TreeNode):
        self.rootNodeList=[-1]
        self.dfs(root,self.rootNodeList)
        self.curIndex=0
        self.countNum=len(self.rootNodeList)-1
        print(self.rootNodeList)
    def next(self) -> int:
        self.curIndex+=1
        return self.rootNodeList[self.curIndex]

    def hasNext(self) -> bool:
        #表示后面还有元素
        if self.curIndex<self.countNum:
            return True
        else:
            return False

    def dfs(self,root,nodeList):
        if root==None:
            return None
        if root.left!=None:
            self.dfs(root.left,nodeList)
        nodeList.append(root.val)
        if root.right!=None:
            self.dfs(root.right,nodeList)

class BSTIterator1:

    def __init__(self, root: TreeNode):
        #维护一个栈
        self.stack=[]
        #栈中只保存根节点和左子树上的各个节点
        while root:
            self.stack.append(root)
            root=root.left

    def next(self) -> int:
        #从栈尾部弹出元素
        cur=self.stack.pop()
        #判断当前的节点是否有右子树
        node=cur.right
        while node:
            self.stack.append(node)
            node=node.left
        return cur.val
    def hasNext(self) -> bool:
        return len(self.stack)>0


# Your BSTIterator object will be instantiated and called as such:
obj = BSTIterator1(root)
param_1 = obj.next()
param_2 = obj.hasNext()
print(param_1)
print(param_2)